/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ZhongJinTao
 * Date: 2024-10-13
 * Time: 15:35
 */
public class Sort {
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 冒泡排序
    public void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            boolean flag = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    swap(arr, j, j + 1);
                }
            }
            if (!flag) break;
        }
    }

    // 直接插入排序
    public void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else break;
            }
            arr[j + 1] = tmp;
        }
    }

    // 希尔排序
    public void shellSort(int[] arr) {
        int gap = arr.length / 2;
        while (gap >= 1) {
            gap /= 2;
            shell(arr, gap);
        }

    }
    public void shell(int[] arr, int gap) {
        int n = arr.length;
        for(int i = gap; i < n; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for(; j >= 0; j--) {
                if(arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                } else break;;
            }
            arr[j + gap] = tmp;
        }
    }

    // 直接选择排序
    public void selectSort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i < n; i++) {
            int minIndex = i;
            for(int j = i + 1; j < n; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, minIndex, i);
        }
    }

    // 快速排序
    public void quickSort(int[] arr) {
        if(arr == null || arr.length == 0) return;
        int left = 0, right = arr.length - 1;
        quick(arr, left, right);
    }
    public void quick(int[] arr, int left, int right)  {
        if(left >= right) return;
        int pivot = partition(arr, left, right);
        quick(arr, left, pivot - 1);
        quick(arr, pivot + 1, right);
    }
    public int partition(int[] arr, int left, int right) {
        int flag = left;
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, flag, left);
        return left;
    }

    // 归并排序
    public void mergeSort(int[] arr) {
        mergeSortFun(arr, 0, arr.length - 1);
    }
    public void mergeSortFun(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSortFun(arr, start, mid);
        mergeSortFun(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
    public void merge(int[] arr, int left, int mid, int right) {
        int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;
        int[] tmp = new int[right - left + 1];
        int cur = 0;
        while (s1 <= e1 && s2 <= e2) {
            if (arr[s1] <= arr[s2]) {
                tmp[cur] = arr[s1++];
            } else {
                tmp[cur] = arr[s2++];
            }
            cur++;
        }
        while (s1 <= e1) {
            tmp[cur++] = arr[s1++];
        }
        while (s2 <= e2) {
            tmp[cur++] = arr[s2++];
        }
        // 添加到原数组中
        for (int i = 0; i < tmp.length; i++) {
            arr[i + left] = tmp[i];
        }
    }
}
